import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 20:20
 * @description 当边的数量接近点的数量，用邻接矩阵存储图，
 */
public class Solution2 {
    /**
     * 邻接矩阵存储图
     */
    int[][] graph;
    /**
     * 判断是否访问过
     */
    boolean[] vis;

    /**
     * 源点到其他点的最短距离，dis[s] = 0, 其他为 +∞
     */
    int[] dis;
    /**
     * 无穷大
     */
    int INF = Integer.MAX_VALUE / 2;

    /**
     * @param n n个结点，编号 0 .. n-1
     * @param s 源点
     * @param edges 边信息
     */
    public void dijkstra(int n, int s, int[][] edges) {
        // 1. 初始化邻接矩阵
        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            // 点到自身的权值为0
            graph[i][i] = 0;
        }
        for (int[] e : edges) {
            graph[e[0]][e[1]] = e[2];
        }
        // 2. 初始化源点到其他点的距离
        dis = new int[n];
        Arrays.fill(dis, INF);
        // 源点到自身的距离为0
        dis[s] = 0;

        // 3. 初始化访问标志
        vis = new boolean[n];

        // 4. 迭代n次
        for (int i = 0; i < n; i++) {
            // 每次找到[最短距离最小] 且 [没有更新] 点 t
            int u = 0, min = INF;
            for (int j = 0; j < n; j++) {
                if (!vis[j] && dis[j] < min) {
                    u = j;
                    min = dis[j];
                }
            }
            vis[u] = true;
            // 用点u的[最小距离]更新其他点
            for (int j = 0; j < n; j++) {
                if (dis[u] + graph[u][j] < dis[j]) {
                    dis[j] = dis[u] + graph[u][j];
                }
            }
        }
    }
}
